package top.minuy.structure.sqrt;

import top.minuy.util.operation.Mergers;

import java.lang.reflect.Array;

/**
 * 类似线段树的区间数据结构
 *
 * @author Minuy
 * @time 17:38
 * @date 2021/11/7
 */
public class SQRT<E> {
    Mergers<E> mergers;
    E[][] data;  // 保存原始数据
    E[] blocks; // 块数据
    int dataSize; // data里数据总量
    int blockCount;  // 块数量
    int blockSize; // 块大小
    Object e;

    public SQRT(E[] array, Mergers<E> mergers) {
        this.mergers = mergers;
        dataSize = array.length;

        if (array.length != 0) {
            e = array[0];
            // 计算分块数量，分块大小
            blockSize = ((int) Math.sqrt(array.length));
            blockCount = (array.length / blockSize) + (array.length % blockSize != 0 ? 1 : 0);
            // 先计算每组的数量，然后再计算组数，否则可能会导致无法容纳，array.length=9998
//        blockCount = ((int) Math.sqrt(array.length));
//        blockSize = blockCount;
//        if ((blockCount * blockCount) < array.length) {
//            blockCount++;
//        }

            // System.out.println(blockCount + ":" + blockSize);
        }
        // 分配数组内存
        this.data = (E[][]) new Object[blockCount][];
        this.blocks = (E[]) new Object[blockCount];

//        IntFunction<E[]> intFunction = E[]::new; //指定要创建的数组类型
//        E[] dates = intFunction.apply(10); //创建一个指定长度的数组


        int initializedSize = 0;
        for (int i = 0; i < this.data.length; i++) {
            int currentSize = blockSize;
            if ((initializedSize + currentSize) > array.length) {
                currentSize = array.length - initializedSize;
            }
            initializedSize += currentSize;
            this.data[i] = (E[]) Array.newInstance(e.getClass(), currentSize);
            // 细心点
            // this.data[i] = (E[]) new Object[initializedSize];
            // System.out.println(initializedSize + ":" + currentSize);
        }
        // 导入数组
        Update(0, array.length, array);
        // importData(0, array.length, array);
//        int arrayIndex = 0;
//        for (int i = 0; i < data.length; i++) {
//            for (int j = 0; j < data[i].length; j++) {
//                // System.out.println("--"+arrayIndex);
//                data[i][j] = array[arrayIndex];
//                arrayIndex++;
//            }
//            // System.out.println(data.length+" : "+data[i].length);
//        }
//        this.array[] = (E[]) new Object[array.length];
//        for (int i = 0; i < array.length; i++) {
//            this.array[i] = array[i];
//        }
        // updateBlocks(0, dataSize);
    }

    /**
     * 取出所有数据
     *
     * @return E[] 返回一个存有所有值的数组
     * @author Minuy
     * @date 2021/11/11 16:00
     */
    public E[] getData() {
        E[] arr = (E[]) new Object[dataSize];
        int arrayIndex = 0;
        for (int i = 0; i < data.length; i++) {
            for (int j = 0; j < data[i].length; j++) {
                arr[arrayIndex] = data[i][j];
                arrayIndex++;
            }
        }
        return arr;
    }

    /**
     * 区间更新[start, start+length)
     *
     * @param start  开始索引
     * @param length 更新长度
     * @param array  更新源数组
     * @author Minuy
     * @date 2021/11/11 9:27
     */
    public void Update(int start, int length, E[] array) {
        if (length == 0) {
            return;
        }
        importData(start, length, array);
        updateBlocks(start, start + length);
    }

    /**
     * 区间导入
     * 从start开始，到length结束，即：[start, start+length)
     *
     * @param start  开始位置
     * @param length 导入长度
     * @param array  导入源
     * @author Minuy
     * @date 2021/11/11 15:58
     */
    private void importData(int start, int length, E[] array) {
        if (start < 0 || start >= dataSize) {
            throw new IllegalArgumentException("Update failed. Index is illegal.");
        }
        if (length < 0 || start + length > dataSize || array.length < length) {
            throw new IllegalArgumentException("Update failed. Length is illegal.");
        }

        // System.out.println("data.length："+data.length);

        int arrayIndex = 0;
        int i = start / blockSize;
        int j = start - (i * blockSize);
        for (; i < data.length; i++) {
            // System.out.println("data["+i+"].length："+data[i].length);
            for (; j < data[i].length; j++) {
                // System.out.println(arrayIndex+":"+array[arrayIndex]+"存入 ["+i+","+j+"]");
                data[i][j] = array[arrayIndex];
                arrayIndex++;
                if (arrayIndex >= length) {
                    // System.out.println(arrayIndex+"~"+length);
                    return;
                }
            }
            j = 0;
            // System.out.println(data.length+" : "+data[i].length);
        }
    }

    /**
     * 区间更新 [s,e)
     *
     * @param left  更新的起始位置
     * @param right 更新的结束位置
     * @author Minuy
     * @date 2021/11/11 7:49
     */
    private void updateBlocks(int left, int right) {
        // System.out.println(s + ":" + e);
        if (left < 0 || right < left || right > dataSize) {
            throw new IllegalArgumentException("UpdateBlocks failed. Index is illegal.");
        }

        // 更新
        int blocksIndexStart = left / blockSize;  // 通过位置计算第一个需要更新的块（向下取整）
        int blocksIndexEnd = (right / blockSize) + (right % blockSize == 0 ? 0 : 1); // 最后一个更新块+1
        // [blocksIndexStart,blocksIndexEnd)
        for (int i = blocksIndexStart; i < blocksIndexEnd; i++) {
            blocks[i] = mergers.merges(data[i]);
        }
    }

    /**
     * 区间查询，查询[left,right]之间的统计
     * 查询结果取决于mergers接口
     *
     * @param left  左索引
     * @param right 右索引
     * @return E 范围的统计数
     * @author Minuy
     * @date 2021/11/11 16:05
     */
    public E range(int left, int right) {
        // right++;
        if (left < 0 || right < left || right >= dataSize) {
            throw new IllegalArgumentException("Range Query failed. Index is illegal.");
        }

        // 在同一个块
        int blockStartIndex = left / blockSize;
        int blockEndIndex = right / blockSize;
        if (blockEndIndex == blockStartIndex) {
            left %= blockSize;
            right %= blockSize;
            E[] mergerArray = (E[]) Array.newInstance(e.getClass(), right - left + 1);
            for (int i = left, k = 0; i <= right; i++, k++) {
                mergerArray[k] = data[blockStartIndex][i];
            }
            return mergers.merges(mergerArray);
        }

        // 开始的那段数据
        int i = left % blockSize;
        E[] mergerArray = (E[]) Array.newInstance(e.getClass(), data[blockStartIndex].length - i);
        for (int j = 0; i < data[blockStartIndex].length; j++, i++) {
            mergerArray[j] = data[blockStartIndex][i];
        }
        E e1 = mergers.merges(mergerArray);

        // 中间的块数据
        E e2 = null;
        if ((blockEndIndex - blockStartIndex - 1) != 0) {
            i = 0;
            mergerArray = (E[]) Array.newInstance(e.getClass(), blockEndIndex - blockStartIndex - 1);
            for (int j = blockStartIndex+1; j < blockEndIndex; j++, i++) {
                mergerArray[i] = blocks[j];
            }
            e2 = mergers.merges(mergerArray);
        }

        // 结尾的那段数据
        i = right % blockSize;
        mergerArray = (E[]) Array.newInstance(e.getClass(), i + 1);
        for (int j = 0; j <= i; j++) {
            mergerArray[j] = data[blockEndIndex][j];
        }
        E e3 = mergers.merges(mergerArray);

        if (e2 == null) {
            mergerArray = (E[]) Array.newInstance(e.getClass(), 2);
            mergerArray[0] = e1;
            mergerArray[1] = e3;
        } else {
            mergerArray = (E[]) Array.newInstance(e.getClass(), 3);
            mergerArray[0] = e1;
            mergerArray[1] = e3;
            mergerArray[2] = e2;
        }
        return mergers.merges(mergerArray);


//        E[] ps = (E[]) Array.newInstance(e.getClass(), 3);
//        E[] bs;
//        int i, j, b, be;
//
//        b = left / blockSize; // 开始位置所在块
//        i = left % blockSize;
//        j = (b + 1) * blockSize;
//
//        boolean isOneBlock = false;
//        if (j > right) {
//            j = right;
//            isOneBlock = true;
//        }
//        j%=blockSize;
//        bs = (E[]) Array.newInstance(e.getClass(), j - i);
//        for (int k = 0; i < j; i++, k++) {
//            bs[k] = data[b][i];
//        }
//        ps[0] = mergers.merges(bs);
//        if (isOneBlock) {
//            return ps[0];
//        }
//
//
//        be = right / blockSize - 1;
//        bs = (E[]) Array.newInstance(e.getClass(), be - b);
//        for (int k = 0; b < be; k++, b++) {
//            bs[k] = blocks[b];
//        }
//        ps[1] = mergers.merges(bs);
//
//        if (right % blockSize == 0) {
//            E[] bt = (E[]) Array.newInstance(e.getClass(), 2);
//            bt[0] = ps[0];
//            bt[1] = ps[1];
//            return mergers.merges(bt);
//        }
//
//        be++;
//        i = be * blockSize;
//        j = i+(right % blockSize);
//        bs = (E[]) Array.newInstance(e.getClass(), j - i);
//        for (int k=0;i<j;i++,k++){
//            bs[k] = data[be][k];
//        }
//        ps[2] = mergers.merges(bs);
//
//        return mergers.merges(ps);
    }
}
